package leetcode.code0087;

public class Solution9 extends Solution87 {

	@Override
	public boolean isScramble(String s1, String s2) {
		char[] cs1 = s1.toCharArray();
		char[] cs2 = s2.toCharArray();
		return this.f(cs1, 0, cs1.length - 1, cs2, 0, cs2.length - 1);
	}

	private boolean f(char[] cs1, int l1, int r1, char[] cs2, int l2, int r2) {
		if (l1 == r1) {
			return cs1[l1] == cs2[l2];
		}
		int len = r1 - l1;
		for (int i = 0; i < len; i++) {// 不能等于len
			boolean p1 = this.f(cs1, l1, l1 + i, cs2, l2, l2 + i);
			boolean p2 = this.f(cs1, l1 + i + 1, r1, cs2, l2 + i + 1, r2);
			if (p1 && p2)
				return true;
			p1 = this.f(cs1, l1, l1 + i, cs2, r2 - i, r2);
			p2 = this.f(cs1, l1 + i + 1, r1, cs2, l2, r2 - i - 1);
			if (p1 && p2)
				return true;
		}
		return false;
	}

	public static void main(String[] args) {
		Solution9 so = new Solution9();
		so.debug1();
		so.debug2();
		so.debug3();
	}

}
